/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package mergesort;

import java.util.Random;

/**
 *
 * @author menderleit
 */
public class MergeSort {

    private static Random rnd;

    private static int[] merge_sort(int[] list) {
        int length = list.length;
        if(length <= 1) return list;
        int[] result = new int[length];
        int middle = length >> 1;                               // length / 2
        int middle2 = middle + (length%2);
        int[] left = new int[middle];
        int[] right = new int[middle2];
        System.arraycopy(list, 0, left, 0, middle);
        System.arraycopy(list, middle, right, 0, middle2);
        left = merge_sort(left);
        right = merge_sort(right);
        result = merge(left, right);
        return result;
    }
    
    private static int[] merge(int[] left, int[] right) {
        int i = 0;
        int[] result = new int[left.length + right.length];
        while(left.length > 0 || right.length > 0) {
            if(left.length > 0 && right.length > 0) {
                if(left[0] < right[0]) {
                    result[i++] = left[0];
                    left = rest(left);
                } else {
                    result[i++] = right[0];
                    right = rest(right);
                }
            } else if(left.length > 0) {
                result[i++] = left[0];
                left = rest(left);
            } else if(right.length > 0) {
                result[i++] = right[0];
                right = rest(right);
            }
        }
        return result;
    }
    
    private static int[] rest(int[] list) {
        int[] result = new int[list.length-1];
        for(int i=1; i<list.length; i++) {
            result[i-1] = list[i];
        }
        return result;
    }
    
    public static void main(String[] args) {
        final int size = 32;
        boolean done;
        rnd = new Random();
        
        int[] list = new int[size];
        for(int i = 0; i < list.length; i++) {
            done = false;
            while(!done) {
                done = true;
                list[i] = rnd.nextInt(80) + 10;
//                for(int j = 0; j < i; j++) {
//                    if(list[i] == list[j]) {
//                        done = false;
//                    }
//                }
            }
            System.out.print(list[i] + " ");
        }
        System.out.println("");
        list = merge_sort(list);
        for(int i=0; i<list.length; i++) {
            System.out.print(list[i] + " ");
        }
        System.out.println("");
    }
}
